public class prog {
    public static void main(String[] args) {
        System.out.println();
    }
}
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode end=head;
        for(int i=0;i<k;i++){
            if(end==null){
                return head;
            }
            end=end.next;
        }
        ListNode prev=null;
        ListNode cur=head;
        while(cur!=end){
            ListNode curnext=cur.next;
            cur.next=prev;
            prev=cur;
            cur=curnext;
        }
        head.next=reverseKGroup(end,k);
        return prev;
    }
}











//import java.util.*;
///*
// * public class ListNode {
// *   int val;
// *   ListNode next = null;
// * }
// *
public class Solution {
    /**
     *
     * @param head ListNode类
     * @param k int整型
     * @return ListNode类
     */
    public ListNode reverseKGroup (ListNode head, int k) {
        // write code here
        ListNode end=head;
        for(int i=0;i<k;i++){
            if(end==null){
                return head;
            }
            end=end.next;
        }
        ListNode prev=null;
        ListNode cur=head;
        while(end!=cur){
            ListNode curnext=cur.next;
            cur.next=prev;
            prev=cur;
            cur=curnext;
        }
        head.next=reverseKGroup(end,k);
        return prev;
    }
}
















/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public void reorderList(ListNode head) {
        if(head==null){
            return ;
        }
        ListNode fast=head;
        ListNode slow=head;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        fast=slow;
        ListNode prev=null;
        while(fast!=null){
            ListNode fastnext=fast.next;
            fast.next=prev;
            prev=fast;
            fast=fastnext;
        }
        fast=prev;
        slow=head;
        while(slow!=fast&&fast!=null){
            if(fast.next==null&&slow!=null){
                break;
            }
            ListNode fastnext=fast.next;
            ListNode slownext=slow.next;
            slow.next=fast;
            fast.next=slownext;
            fast=fastnext;
            slow=slownext;
        }
    }
}













/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    TreeNode head=null;
    TreeNode prev=null;
    public TreeNode convertBiNode(TreeNode root) {
        if(root==null){
            return null;
        }
        convertBiNode(root.left);
        if(head==null){
            head=root;
        }else{
            prev.right=root;
        }
        prev=root;
        root.left=null;
        convertBiNode(root.right);
        return head;
    }
}












public class ListNode{
    String val;
    ListNode next;
    ListNode prev;
    ListNode(String x){
        this.val=x;
    }
}
class BrowserHistory {
    ListNode cur;
    public BrowserHistory(String homepage) {
        this.cur=new ListNode(homepage);
    }

    public void visit(String url) {
        if(cur.next!=null){
            cur.next=null;
        }
        ListNode data=new ListNode(url);
        cur.next=data;
        data.prev=cur;
        cur=cur.next;
    }

    public String back(int steps) {
        while(steps>0&&cur.prev!=null){
            cur=cur.prev;
            steps--;
        }
        return cur.val;
    }

    public String forward(int steps) {
        while(steps>0&&cur.next!=null){
            cur=cur.next;
            steps--;
        }
        return cur.val;
    }
}
/**
 * Your BrowserHistory object will be instantiated and called as such:
 * BrowserHistory obj = new BrowserHistory(homepage);
 * obj.visit(url);
 * String param_2 = obj.back(steps);
 * String param_3 = obj.forward(steps);
 */













public class ListNode{
    int val;
    ListNode next;
    ListNode(int x){
        this.val=x;
    }
}
class MyCircularQueue {
    ListNode head=null;
    ListNode tail=null;
    int count;
    int capacity;
    public MyCircularQueue(int k) {
        this.capacity=k;
        this.count=0;
    }

    public boolean enQueue(int value) {
        if(this.capacity==this.count){
            return false;
        }
        ListNode data=new ListNode(value);
        if(this.count==0){
            this.head=data;
            this.tail=data;
        }else{
            this.tail.next=data;
            this.tail=data;
        }
        this.count++;
        return true;
    }

    public boolean deQueue() {
        if(this.count==0){
            return false;
        }
        this.head=this.head.next;
        this.count--;
        return true;
    }

    public int Front() {
        return this.count==0?-1:this.head.val;
    }

    public int Rear() {
        return this.count==0?-1:this.tail.val;
    }

    public boolean isEmpty() {
        return this.count==0;
    }

    public boolean isFull() {
        return this.capacity==this.count;
    }
}
/**
 * Your MyCircularQueue object will be instantiated and called as such:
 * MyCircularQueue obj = new MyCircularQueue(k);
 * boolean param_1 = obj.enQueue(value);
 * boolean param_2 = obj.deQueue();
 * int param_3 = obj.Front();
 * int param_4 = obj.Rear();
 * boolean param_5 = obj.isEmpty();
 * boolean param_6 = obj.isFull();
 */
















public class Node{
    int val;
    Node next;
    Node prev;
    Node(int x){
        this.val=x;
        this.next=null;
        this.prev=null;
    }
}
class MyCircularDeque {
    Node head=null;
    Node fast=null;
    int count;
    int capacity;
    /** Initialize your data structure here. Set the size of the deque to be k. */
    public MyCircularDeque(int k) {
        this.count=0;
        this.capacity=k;
    }

    /** Adds an item at the front of Deque. Return true if the operation is successful. */
    public boolean insertFront(int value) {
        if(this.count==this.capacity){
            return false;
        }
        Node data=new Node(value);
        if(this.count==0){
            this.head=data;
            this.fast=data;
        }else{
            this.head.prev=data;
            data.next=this.head;
            this.head=data;
        }
        this.count++;
        return true;
    }

    /** Adds an item at the rear of Deque. Return true if the operation is successful. */
    public boolean insertLast(int value) {
        if(this.count==this.capacity){
            return false;
        }
        Node data=new Node(value);
        if(this.head==null){
            this.head=data;
            this.fast=data;
        }else{
            this.fast.next=data;
            data.prev=fast;
            fast=data;
        }
        this.count++;
        return true;
    }

    /** Deletes an item from the front of Deque. Return true if the operation is successful. */
    public boolean deleteFront() {
        if(this.count==0){
            return false;
        }
        if(this.count==1){
            this.head=this.fast=null;
        }else{
            Node headnext=this.head.next;
            this.head.next=null;
            this.head=headnext;
            this.head.prev=null;
        }
        this.count--;
        return true;
    }

    /** Deletes an item from the rear of Deque. Return true if the operation is successful. */
    public boolean deleteLast() {
        if(this.count==0){
            return false;
        }
        if(this.count==1){
            this.head=this.fast=null;
        }else{
            Node fastprev=fast.prev;
            fast.prev=null;
            fast=fastprev;
            fast.next=null;
        }
        this.count--;
        return true;
    }

    /** Get the front item from the deque. */
    public int getFront() {
        return this.count>0?this.head.val:-1;
    }

    /** Get the last item from the deque. */
    public int getRear() {
        return this.count>0?this.fast.val:-1;
    }

    /** Checks whether the circular deque is empty or not. */
    public boolean isEmpty() {
        return this.count==0;
    }

    /** Checks whether the circular deque is full or not. */
    public boolean isFull() {
        return this.count==this.capacity;
    }
}
/**
 * Your MyCircularDeque object will be instantiated and called as such:
 * MyCircularDeque obj = new MyCircularDeque(k);
 * boolean param_1 = obj.insertFront(value);
 * boolean param_2 = obj.insertLast(value);
 * boolean param_3 = obj.deleteFront();
 * boolean param_4 = obj.deleteLast();
 * int param_5 = obj.getFront();
 * int param_6 = obj.getRear();
 * boolean param_7 = obj.isEmpty();
 * boolean param_8 = obj.isFull();
 */











public class ListNode{
    public int val;
    public ListNode next;
    public ListNode(int x){
        val=x;
    }
}
class MyLinkedList {
    int size=0;
    ListNode head;
    /** Initialize your data structure here. */
    public MyLinkedList() {
        size=0;
        head=new ListNode(0);
    }

    /** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
    public int get(int index) {
        if(index<0||index>=size){
            return -1;
        }
        ListNode cur=head;
        for(int i=0;i<index+1;i++){
            cur=cur.next;
        }
        return cur.val;
    }

    /** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
    public void addAtHead(int val) {
        addAtIndex(0,val);
    }

    /** Append a node of value val to the last element of the linked list. */
    public void addAtTail(int val) {
        addAtIndex(size,val);
    }

    /** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
    public void addAtIndex(int index, int val) {
        if(index>size){
            return ;
        }
        if(index<0){
            index=0;
        }
        size++;
        ListNode prev=head;
        while(index>0){
            prev=prev.next;
            index--;
        }
        ListNode data=new ListNode(val);
        data.next=prev.next;
        prev.next=data;
    }

    /** Delete the index-th node in the linked list, if the index is valid. */
    public void deleteAtIndex(int index) {
        if(index<0||index>=size){
            return ;
        }
        ListNode prev=head;
        while(index>0){
            prev=prev.next;
            index--;
        }
        size--;
        prev.next=prev.next.next;
    }
}
/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList obj = new MyLinkedList();
 * int param_1 = obj.get(index);
 * obj.addAtHead(val);
 * obj.addAtTail(val);
 * obj.addAtIndex(index,val);
 * obj.deleteAtIndex(index);
 */













/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/
class Solution {
    Map<Node, Node> map = new HashMap<Node,Node>();
    public Node copyRandomList(Node head) {
        if(head==null){
            return null;
        }
        while(!map.containsKey(head)){
            Node newhead=new Node(head.val);
            map.put(head,newhead);
            newhead.next=copyRandomList(head.next);
            newhead.random=copyRandomList(head.random);
        }
        return map.get(head);
    }
}









/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/

class Solution {
    Map<Node, Node> cachedNode = new HashMap<Node,Node>();
    public Node copyRandomList(Node head) {
        if(head==null){
            return null;
        }
        if(!cachedNode.containsKey(head)){
            Node newhead=new Node(head.val);
            cachedNode.put(head,newhead);
            newhead.next=copyRandomList(head.next);
            newhead.random=copyRandomList(head.random);
        }
        return cachedNode.get(head);
    }
}










/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode insertionSortList(ListNode head) {
        if(head==null){
            return null;
        }
        ListNode newhead = new ListNode(0);
        newhead.next=head;
        ListNode cur=head.next;
        ListNode last=head;
        while(cur!=null){
            if(last.val<=cur.val){
                last=last.next;
            }else{
                ListNode prev=newhead;
                while(prev.next.val<=cur.val){
                    prev=prev.next;
                }
                last.next=cur.next;
                cur.next=prev.next;
                prev.next=cur;
            }
            cur=last.next;
        }
        return newhead.next;
    }
}










/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode sortList(ListNode head) {
        return mergesort(head);
    }
    public ListNode mergesort(ListNode head){
        if(head==null||head.next==null){
            return head;
        }
        ListNode fast=head.next;
        ListNode slow=head;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        ListNode head2=slow.next;
        slow.next=null;
        return merge(mergesort(head),mergesort(head2));
    }
    public ListNode merge(ListNode l,ListNode r){
        ListNode newhead=new ListNode(-1);
        ListNode cur=newhead;
        while(l!=null&&r!=null){
            if(l.val<r.val){
                cur.next=l;
                l=l.next;
            }else{
                cur.next=r;
                r=r.next;
            }
            cur=cur.next;
        }
        if(l!=null){
            cur.next=l;
        }
        if(r!=null){
            cur.next=r;
        }
        return newhead.next;
    }
}










/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public int numComponents(ListNode head, int[] nums) {
        Set<Integer> Gset=new HashSet<>();
        for(int x: nums){
            Gset.add(x);
        }

        ListNode cur=head;
        int count=0;
        while(cur!=null){
            if(Gset.contains(cur.val)&&(cur.next==null||!Gset.contains(cur.next.val))){
                count++;
            }
            cur=cur.next;
        }
        return count;
    }
}













/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public int[] nextLargerNodes(ListNode head) {
        List<Integer> list=new ArrayList<>();
        while(head!=null){
            list.add(head.val);
            head=head.next;
        }
        int[] arr=new int[list.size()];
        for(int i=0;i<list.size()-1;i++){
            for(int j=i+1;j<list.size();j++){
                if(list.get(j)>list.get(i)){
                    arr[i]=list.get(j);
                    break;
                }
            }
        }
        return arr;
    }
}











/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeZeroSumSublists(ListNode head) {
        ListNode newhead=new ListNode(-1);
        ListNode prev=newhead;
        newhead.next=head;
        while(prev!=null){
            int sum=0;
            ListNode cur=prev.next;
            while(cur!=null){
                sum+=cur.val;
                if(sum==0){
                    prev.next=cur.next;
                    break;
                }else{
                    cur=cur.next;
                }
            }
            if(cur==null){
                prev=prev.next;
            }
        }
        return newhead.next;
    }
}












/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head==null){
            return null;
        }
        ListNode fast=head;
        ListNode slow=head;
        while(true){
            if(fast==null||fast.next==null){
                return null;
            }
            fast=fast.next.next;
            slow=slow.next;
            if(slow==fast){
                break;
            }
        }
        fast=head;
        while(fast!=slow){
            fast=fast.next;
            slow=slow.next;
        }
        return fast;
    }
}














/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode[] splitListToParts(ListNode head, int k) {
        int len=0;
        ListNode cur=head;
        while(cur!=null){
            cur=cur.next;
            len++;
        }
        int width=len/k;
        int rem=len%k;
        ListNode[] list=new ListNode[k];
        cur=head;
        for(int i=0;i<k;i++){
            ListNode newhead=new ListNode(0);
            ListNode data=newhead;
            for(int j=0;j<width+(i<rem?1:0);j++){
                data.next=new ListNode(cur.val);
                data=data.next;
                cur=cur.next;
            }
            list[i]=newhead.next;
        }
        return list;
    }
}











/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if(l1==null){
            return l2;
        }
        if(l2==null){
            return l1;
        }
        ListNode prev1=null;
        ListNode prev2=null;
        ListNode cur1=l1;
        ListNode cur2=l2;
        while(cur1!=null){
            ListNode cur1next=cur1.next;
            cur1.next=prev1;
            prev1=cur1;
            cur1=cur1next;
        }
        while(cur2!=null){
            ListNode cur2next=cur2.next;
            cur2.next=prev2;
            prev2=cur2;
            cur2=cur2next;
        }
        cur1=prev1;
        cur2=prev2;
        int tmp=0;
        int count=0;
        int sum=0;
        ListNode newhead=new ListNode(-1);
        ListNode cur=newhead;
        while(cur1!=null&&cur2!=null){
            count=cur1.val+cur2.val+tmp;
            tmp=count/10;
            sum=count%10;
            cur.next=new ListNode(sum);
            cur=cur.next;
            cur1=cur1.next;
            cur2=cur2.next;
        }
        while(cur1!=null){
            count=cur1.val+tmp;
            tmp=count/10;
            sum=count%10;
            cur.next=new ListNode(sum);
            cur=cur.next;
            cur1=cur1.next;
        }
        while(cur2!=null){
            count=cur2.val+tmp;
            tmp=count/10;
            sum=count%10;
            cur.next=new ListNode(sum);
            cur=cur.next;
            cur2=cur2.next;
        }
        if(tmp>0){
            cur.next=new ListNode(tmp);
        }
        ListNode prev=null;
        cur=newhead.next;
        while(cur!=null){
            ListNode curnext=cur.next;
            cur.next=prev;
            prev=cur;
            cur=curnext;
        }
        return prev;
    }
}












/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    ListNode head;
    /** @param head The linked list's head.
    Note that the head is guaranteed to be not null, so it contains at least one node. */
    public Solution(ListNode head) {
        this.head=head;
    }

    /** Returns a random node's value. */
    public int getRandom() {
        if(head==null){
            return -1;
        }
        Random random=new Random();
        ListNode cur=head;
        int val=cur.val;
        cur=cur.next;
        int i=1;
        while(cur!=null){
            i++;
            if(random.nextInt(i)==0){
                val=cur.val;
            }
            cur=cur.next;
        }
        return val;
    }
}
/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(head);
 * int param_1 = obj.getRandom();
 */













/*
// Definition for a Node.
class Node {
    public int val;
    public Node next;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _next) {
        val = _val;
        next = _next;
    }
};
*/
class Solution {
    public Node insert(Node head, int insertVal) {
        if(head==null){
            Node H=new Node(insertVal,null);
            H.next=H;
            return H;
        }
        if(head.next==null){
            head.next=new Node(insertVal,head);
            return head;
        }
        Node cur=head.next;
        Node prev=head;
        while(true){
            if(prev.val<=insertVal&&insertVal<=cur.val){
                prev.next=new Node(insertVal,cur);
                return head;
            }
            if(prev.val>cur.val){
                if(prev.val<insertVal&&cur.val<insertVal){
                    prev.next=new Node(insertVal,cur);
                    return head;
                }else if(prev.val>=insertVal&&cur.val>=insertVal){
                    prev.next=new Node(insertVal,cur);
                    return head;
                }
            }
            prev=cur;
            cur=cur.next;
            if(prev==head){
                break;
            }
        }
        prev.next=new Node(insertVal,cur);
        return head;
    }
}













/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode sortList(ListNode head) {
        return mergesort(head);
    }
    public ListNode mergesort(ListNode head){
        if(head==null||head.next==null){
            return head;
        }
        ListNode fast=head.next;
        ListNode slow=head;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        ListNode head2=slow.next;
        slow.next=null;
        ListNode l=mergesort(head);
        ListNode r=mergesort(head2);
        return merge(l,r);
    }
    public ListNode merge(ListNode l,ListNode r){
        ListNode newhead=new ListNode(-1);
        ListNode cur=newhead;
        while(l!=null&&r!=null){
            if(l.val<r.val){
                cur.next=l;
                l=l.next;
            }else{
                cur.next=r;
                r=r.next;
            }
            cur=cur.next;
        }
        if(l!=null){
            cur.next=l;
        }
        if(r!=null){
            cur.next=r;
        }
        return newhead.next;
    }
}
















/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public void reorderList(ListNode head) {
        if(head==null){
            return;
        }
        ListNode fast=head;
        ListNode slow=head;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        fast=slow;
        ListNode prev=null;
        while(fast!=null){
            ListNode fastnext=fast.next;
            fast.next=prev;
            prev=fast;
            fast=fastnext;
        }
        slow=head;
        fast=prev;
        while(slow!=fast&&fast!=null){
            if(fast.next==null&&slow!=null){
                break;
            }
            ListNode slownext=slow.next;
            ListNode fastnext=fast.next;
            slow.next=fast;
            fast.next=slownext;
            slow=slownext;
            fast=fastnext;

        }
        return ;
    }
}










/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if(l1==null){
            return l2;
        }
        if(l2==null){
            return l1;
        }
        ListNode newhead=new ListNode(-1);
        ListNode cur=newhead;
        ListNode cur1=l1;
        ListNode prev1=null;
        while(cur1!=null){
            ListNode nextcur1=cur1.next;
            cur1.next=prev1;
            prev1=cur1;
            cur1=nextcur1;
        }
        ListNode cur2=l2;
        ListNode prev2=null;
        while(cur2!=null){
            ListNode nextcur2=cur2.next;
            cur2.next=prev2;
            prev2=cur2;
            cur2=nextcur2;
        }
        int count=0;
        int sum=0;
        int tmp=0;
        cur1=prev1;
        cur2=prev2;
        while(cur1!=null&&cur2!=null){
            count=cur1.val+cur2.val+tmp;
            sum=count%10;
            tmp=count/10;
            cur.next=new ListNode(sum);
            cur=cur.next;
            cur1=cur1.next;
            cur2=cur2.next;
        }
        while(cur1!=null){
            count=cur1.val+tmp;
            sum=count%10;
            tmp=count/10;
            cur.next=new ListNode(sum);
            cur=cur.next;
            cur1=cur1.next;
        }
        while(cur2!=null){
            count=cur2.val+tmp;
            sum=count%10;
            tmp=count/10;
            cur.next=new ListNode(sum);
            cur=cur.next;
            cur2=cur2.next;
        }
        if(tmp>0){
            cur.next=new ListNode(tmp);
        }
        ListNode prev=null;
        cur=newhead.next;
        while(cur!=null){
            ListNode curnext=cur.next;
            cur.next=prev;
            prev=cur;
            cur=curnext;
        }
        return  prev;
    }
}